/**
 * @file     lengthOfLIS.js
 * @brief    [300. 最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
 * @author   Zhu
 * @date     2022-04-01 14:00
 */

/**
 * 动态规划
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    const dp = [];

    let globalMax = 0;
    for (let i = 0; i < nums.length; i++) {
        let localMax = 0;
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (localMax < dp[j]) localMax = dp[j]; // 局部最优
            }
        }
        dp[i] = localMax + 1;
        if (globalMax < dp[i]) globalMax = dp[i]; // 全局最优
    }

    return globalMax;
};

/**
 * 贪心+二分
 */
var lengthOfLIS = function (nums) {
    const tails = [nums[0]]; // 记录长度为i的子序列的尾巴
    for (let i = 1; i < nums.length; i++) {
        let low = 0,
            high = tails.length - 1;
        // 能够形成新的递增序列
        if (tails[high] < nums[i]) {
            tails.push(nums[i]);
            continue;
        }
        // 更新尾巴数组
        while (low < high) {
            let mid = Math.floor((high + low) / 2);
            if (tails[mid] < nums[i]) low = mid + 1;
            else high = mid;
        }
        tails[low] = nums[i];
    }

    return tails.length;
};
